import java.util.Stack;

public class Offer31 {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i=0,j=0;
        for (; i <pushed.length; i++) {
            stack.push(pushed[i]);
            while(stack.size()>0&&stack.peek()==popped[j]){
                stack.pop();
                j++;
            }
        }
        while (stack.size()!=0){
            if (stack.pop()!=popped[j]){
                return false;
            }
            j++;
        }
        return true;
    }
}
